package day1.linkedlist;

import java.util.Collection;
import java.util.List;
import java.util.Map;

/**
 * @author pacai
 * @version 1.0
 */
@SuppressWarnings("all")
public class ReverseNodesinGroups {
    private class Node<V> {
        V data;
        Node<V> next;
//        Node<V> last;

        public Node(V data) {
            this.data = data;
        }


//        public Node reverseKGroup(Node head, int k) {
//            Node start = head;
//            Node end = getGroupEnd(start, k);
//            if(end == null) return head;
//            head = end;
//            reverse(start, end);
//            Node lastEnd = start;
//            while (lastEnd.next != null) {
//                start = lastEnd.next;
//                end = getGroupEnd(start, k);
//                if (end == null) return head;
//                reverse(start, end);
//                lastEnd.next = end;
//                lastEnd = start;
//            }
//            return head;
//        }

        public Node reverseKGroup(Node head, int k) {
            Node start = head;
            Node end = head;
            Node returnHead = getGroupEnd(start, k);
            Node lastEnd = start;
            while (lastEnd.next != null) {
                start = lastEnd.next;
                if ((end = getGroupEnd(end, k)) == null) {
                    break;

                }
                reverse(start, end);
                lastEnd.next = end;
                lastEnd = start;
            }
            return returnHead == null ? head : returnHead;
        }

        public Node getGroupEnd(Node start, int k) {
            while (--k != 0 && start != null)
                start = start.next;
            return start;
        }

        public void reverse(Node start, Node end) {
            end = end.next;
            Node pre = null;
            Node next = null;
            Node cur = start;

            while (cur != null) {
                next = cur.next;
                cur.next = pre;
                pre = cur;
                cur = next;
            }
            start.next = end;
        }
    }
}